COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00003 00003	.NOFILL
C00007 ENDMK
C⊗;
.device xgp
.evenleftborder ← oddleftborder ← 1000;
.font 1 "baxl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "baxm30" <<var>>
.font 4 "basb30" <<bold>>
.font 5 "bdr30" <<const>>
.PAGE FRAME 53 HIGH 200 WIDE;
.AREA TEXT LINES 4 TO 51 CHARS 1 TO 200;
.PLACE TEXT;
.NARROW 0,200-81;
.INDENT 0,0,0;
.turn on "%α" ;
.NOFILL
%5                                206 MIDTERM SOLUTIONS%1




1. (a)	%3element1[u,n] ← %4 if n %3u %4then %5ERROR %4else ifα
%3eq[n,1] %4 then a %3u %4else %3element1[%4d %3u,n-1]%1

   (b)  %3element2[x,s] ← 
%4if n %3s %4then %3x %4 else if %3at[x] %4then %5ERROR α
%4else %3element2[%4if eq%3[%4a %3s,%5A%3] %4then a %3x %4else d %3x,%4d %3s]%1

2. (a)  %3selectatoms1[u] ← %4if n %3u %4then %5NIL %4else if at a%3[u] %4then a%3[u].selectatoms1[%4d %3u] 
%4else %3selectatoms1[%4d %3u]%1

   (b)  %3selectatoms2[x] ← selat2[x,%5NIL%3]
selat2[x,v] ← %4if at %3x %4then if %3member[x,v] %4then %3v %4else %3x.v %4else %3selat2[%4a %3x,selat2[%4d %3x,v]]%1

   (c)  %3select1[p,u] ← %4if n %3u %4then %5NIL %4else if %3p %4a %3u %4then α
a%3[u].select1[p,%4d %3u] %4else %3select1[p,%4d %3u]%1

   (d)  %3select2[p,x] ←
%3{%4if %3p x %4then %4list %3x %4else %5NIL%3}α
[λ w.%4if at %3x %4then %3w %4else %3w * [select2[p,%4a %3x] * select2[p,%4d %3x]]]%1

   (e)  %3select3[p,x] ← sel3[p,x,%5NIL%3]
%3sel3[p,x,s] ←    %3{%4if %3p x %4then list %3reverse[s] %4else %5NIL%3}
[λ w.%4if at %3x %4then %3w %4else %3w * [select2[p,%4a %3x,%5A.%3s] * select2[p,%4d %3x,%5D%3.s]]]%1

3. (a)  %3find[x,p] ← f[%4list %3x,p,%5NIL%3]
f[u,p,seen] ← %4if n %3u %4then %5NIL %4else if %3p %4a %3u %4then a %3u %4else %3{f[%4d %3u,p,%4a %3u.seen]}
[λw.%4if %3w %4then %3w %4else %3f[dif[successors[%4a %3u],seen],p,%4a%3[u].seen]]

   (b)  %3findall[x,p] ← fa[%4list %3x,p,%5NIL]
%3fa[u,p,seen] ← %4if n %3u %4then %5NIL %4else %3union[if %3p %4a %3u %4then list%3[%4a %3u] %4else %5NIL%3],
union[fa[%4d %3u,p,%4a %3u.seen],fa[dif[successors[%4a %3u],seen],p,%4a%3[u].seen]]]%1

4. %3ok[π] ← ok2[π,%5NIL,NIL%3]
ok2[π,ld,lu] ← %4if n %3π %4then [if %3dif[lu,ld] then %5NIL%4 else %5T%4] else
if at%3[%4a %3π] %4then [if %3member[a %3π,ld] %4then %5NIL %4else %3ok2[%4d %3π,%4a%3[π].ld,lu]] %4else
if eq[a a %3π,%5GO%4] then %3ok2[%4d %3π,ld,%3union[%4d a %3π,lu]] %4else
if eq[a a %3π,%5IF%4] then %3ok2[%4d %3π,ld,%3union[%4d d a %3π,lu]] %4else
%3ok2[%4d %3π,ld,lu]%1

%3dif %1and %3union %1are given by:

%3dif[u,v] ← %4if n %3u %4then %5NIL %4else if %3member[%4a %3u,v] %4then %3dif[%4d %3u,v] %4else a%3[u].dif[%4d %3u,v]

%3union[u,v] ← %4if n %3u %4then %3v %4else if %3member[%4a %3u,v] %4then %3union[%4d %3u,v] %4else a%3[u].union[%4d %3u,v]